import numpy


def getKjMin(near, k, line, cost):
    minc=9999
    j_min=0
    for j in range(1, line+1):
        if near[j]==0 and cost[k-1, j-1]<minc:
            minc=cost[k-1, j-1]
            j_min=j
    return minc, j_min


def primArithmatic(cost):
    # 获取最小成本的边
    mincost = 999999
    [row, line] = cost.shape
    # 初始化一个T矩阵用来存放最小生成树的边
    T=[[0 for i in range(2)]for i in range(line-1)]
    T=numpy.array(T)
    for i in range(row):
        for j in range(line):
            if i > j and cost[i, j] < mincost:
                mincost = cost[i, j]
                k, l = i+1, j+1
    T[1-1, 1-1], T[1-1, 2-1]=k, l
    # 初始化一个near
    near={key: "" for key in range(1, row+1)}
    # 将near 置初值
    for i in range(1, row+1):
        if cost[i-1, l-1]<cost[i-1, k-1]:
            near[i]=l
        else:
            near[i]=k
    near[k]=near[l]=0
    for h in range(2, line):
        costj = 99999
        n=0  # 用来存放cost(j,NEAR(j))最小的下标
        for j in range(1, row + 1):
            if near[j] != 0:
                if cost[j - 1, near[j] - 1] < costj:
                    costj = cost[j - 1, near[j] - 1]
                    n=j
        mincost=mincost+costj
        T[h-1, 1-1], T[h-1, 2-1]= n, near[n]
        near[n]=0
        # 修改near
        j=0
        for k in range(1, line+1):
            if near[k]!=0:
                minc, j=getKjMin(near, k, line, cost)
                if cost[k-1, near[k]-1]> minc:
                    near[k] = j
    return T.tolist()

